\chapter{Partie 4}

\section{Lecture des traces}
Nous avons donc à notre disposition deux types de traces : les traces dynamiques et les traces statiques.
Ces traces doivent être lues par un parseur puis analysées de manière séparée, et correlée.
Le parseur devra donc pourvoir lire les deux types de traces.

Nous avons donc mis en place, à l'aide des outils {\tt lex} et {\tt yacc}, un parseur qui reconnaît la grammaire définie ci-dessous~:

\begin{lstlisting}{language=yacc}
Analyse_Traces :
		Fichier_Trace_Statique Fichier_Trace_Dynamique

Fichier_Trace_Statique :
		ListeTracesStatiques

ListeTracesStatiques :
		TraceStatique ListeTracesStatiques		
		| TraceStatique		

TraceStatique :
		FUNCTION ID NB LOADS NB STORES			

Fichier_Trace_Dynamique : 
		ListeTracesDynamiques

ListeTracesDynamiques :
		TraceDynamique ListeTracesDynamiques
		| TraceDynamique

TraceDynamique : 
		CALL NB REQUIRED NB FUNCTION ID ENTRY NB EXIT NB
\end{lstlisting}
Une analyse de trace complète est constituée d'un fichier de traces statiques et d'un fichier de traces dynamiques. Un fichier de traces statiques est composée d'une ou plusieurs traces statiques. Et enfin une trace statique est composée d'une suite bien définie de lexèmes. Le même principe est appliqué pour le fichier de traces dynamiques.

Le parseur charge les traces dans des structures prévues à cet effet, et remplit des vecteurs.

\section{Traitement des traces dynamiques}
Il s'agit de calculer les temps exclusifs passés dans chaque fonction. Le temps exclusif est le temps passé dans une fonction, sans le temps passé dans les fonctions appelées par cette même fonction.

\subsection{Calcul des Temps Exclusifs}
\subsubsection{Algorithme}

\noindent Nous partons des constats simples suivants : 
\begin{itemize}
	\item Les appels de fonctions constituent une pile
	\item La dernière fonction appelée n'en appelle aucune autre : sont temps inclusif est donc égal à son temps exclusif.
\end{itemize}

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=15cm]{images/pile}
		\caption{Exemple de pile d'appels de fonction}
	\end{center}
\end{figure}

Pour calculer les temps exclusifs, une méthode consiste donc à partir de la fin. Pour chaque nouvelle fonction rencontrée, tester si elle inclut d'autres fonctions, ce que nous pouvons faire facilement puisque nous avons les timestamps de début et de fin d'exécution de chaque fonction. Si des fonctions sont incluses, déduire leurs temps exclusifs calculés précédemment du temps inclusif de la fonction en cours de calcul. Et ainsi de suite jusqu'à la fonction main.

\noindent Par exemple, pour la figure 5.1 le calcul serait le suivant :
\begin{verbatim}
\\ E est la dernière fonction appelée
-> Temps_Exclusif(E) = Temps_Inclusif(E)

\\ Calcul pour D
- E est inclus dans D
-> Temps_Exclusif(D) = Temps_Inclusif(D) - Temps_Exclusif(E)

\\ Calcul pour C
- D n'est pas inclus dans C
-> Temps_Exclusif(C) = Temps_Inclusif(C)

\\ Calcul pour B
- C est inclus dans B
-> Temps_Exclusif(B) = Temps_Inclusif(B) - Temps_Exclusif(C)

\\ Calcul pour A
- B et C sont inclus dans A
-> Temps_Exclusif(A) = Temps_Inclusif(A) - Temps_Exclusif(C) 
- Temps_Exclusif(B)

\\ Calcul pour main
- A, B, C, D et E sont inclus dans main
-> Temps_Exclusif(main) = Temps_Inclusif(main) - Temps_Exclusif(A) 
- Temps_Exclusif(B) - Temps_Exclusif(C) - Temps_Exclusif(D) 
- Temps_Exclusif(E) 
\end{verbatim}

\subsubsection{Résultat}
\noindent En sortie, nous obtenons l'affichage suivant :
\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=15cm]{images/Temps_Exclusif}
		\caption{Résultat du calcul des temps exclusifs}
	\end{center}
\end{figure}

\subsection{Agrégation des temps d'exécution}
Les traces dynamiques font apparaître tous les appels de fonction et il arrive qu'une même fonction soit appelée à plusieurs reprises. Il est donc intéressant de connaître le nombre d'appels à une même fonction, le temps exclusif total passé ainsi que le temps exclusif moyen. Etant donné que nous avons également à disposition le temps d'exécution inclusif de la fonction {\tt main}, les pourcentages de temps d'exécution de chaque fonction par rapport au temps d'exécution du programme peuvent être calculés.

\noindent Le résultat obtenu se présente sous la forme suivante : 
\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=15cm]{images/avg}
		\caption{Agrégation des données dynamiques}
	\end{center}
\end{figure}

\section{Fusion avec les traces statiques}
Nous avons d'un côté les résultats de l'analyse dynamique et l'autre les nombres de chargements et d'écritures en mémoire par fonction. Il est donc possible de lier les deux, et de multiplier les charges en lecture et en écriture par le nombre d'appels de fonctions.

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=15cm]{images/recap}
		\caption{Fusion des données statiques et dynamiques}
	\end{center}
\end{figure}

\section{Plotter}
Le parser génère également des fichiers de données, un par fonction, destinés à être affichés à l'aide de gnuplot. Le fichier gnuplot est également généré par le parser, car son contenu dépend des fonctions instrumentées par l'utilisateur.

\section{Sortie}
En définitive, nous obtenons deux types de sorties~: des graphiques représentant les temps inclusifs et exclusifs par fonction, et un histogramme représentant les pourcentages de temps passés par fonctions ainsi que les pourcentages de lectures et d'écritures en mémoire.

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=15cm]{images/Incl_Excl}
		\caption{Exemple de graphique représentant les temps inclusif et exclusif}
	\end{center}
\end{figure}

mémoire.

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=15cm]{images/histo}
		\caption{Exemple d'histogramme obtenu}
	\end{center}
\end{figure}